/*
题目链接 : https://leetcode.cn/problems/longest-common-prefix-of-k-strings-after-removal/description/
*/

//题解代码:
class Solution {
public:
    int tree[100005][26];
    int pass[100005];
    int cnt = 0;
    int fid=0,sid=0;
    int flen=0,slen=0;
    void add(string& s){
        pass[0]++;
        for(int i=0,path=0,cur=0;i<s.size();++i){
            path = s[i]-'a';
            if(tree[cur][path]==0){
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
    }

    vector<int> longestCommonPrefix(vector<string>& words, int k) {
        memset(tree,0,sizeof(tree));
        memset(pass,0,sizeof(pass));
        cnt = 0;
        for(auto& s : words) add(s);

        int n = words.size();
        for(int i=0;i<n;++i){
            auto& s = words[i];
            int j=0;
            int cur = 0;
            for(;j<s.size();++j){
                int path = s[j]-'a';
                int pre = cur;
                cur = tree[cur][path];
                if(pass[cur]<k){
                    cur = pre;
                    break;
                }
            }
            if(j>flen){
                sid = fid;
                slen = flen;
                flen = j;
                fid = cur;
            }else if(j>slen && cur!=fid){
                sid = cur;
                slen = j;
            }
        }
        vector<int> ans(n,0);
        for(int i=0;i<n;++i){
            auto& s = words[i];
            int cur=0,j=0;
            for(;j<s.size();++j){
                int path = s[j]-'a';
                int pre=cur;
                cur = tree[cur][path];
                if(pass[cur]<k){
                    cur = pre;
                    break;
                }
            }
            if(cur!=fid){
                ans[i] = flen;
            }else if(pass[fid]>k){
                ans[i] = flen;
            }else{
                ans[i] = slen;
            }
        }
        return ans;
    }
};
